package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author Lzm
 * @version 1.0
 */
/*与之前题不同的是
* 去重操作不能先给数组排序
* 之前的题去重, 首先给nums数组进行排序
*
* 去重操作难
* */
public class findSubsequences_ {
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new LinkedList<>();

  boolean[] used;
  @Test
  public void findSubsequencesTest(){
    int[] nums = new int[]{4,7,6,7};
    used = new boolean[nums.length];
    Arrays.fill(used,false);
    backTracking(nums,0);

    System.out.println(result);
  }



  public void backTracking(int[] nums,int index){
    if (list.size() >= 2){
      result.add(new LinkedList<>(list));
    }
    Set<Integer> set = new HashSet<>();
    for (int i = index ; i < nums.length ; i++){
        if (list.size() != 0 && nums[i] < list.get(list.size() - 1) || set.contains(nums[i])){
          continue;
        }
            set.add(nums[i]);
            list.add(nums[i]);
            backTracking(nums , i + 1);
            list.removeLast();
        }
    }
  }
